package com.ainge.easystudy.binary.tree;

/**
 * 判断链表是否有环
 *
 * @author: Ainge
 * @Time: 2021/9/16 22:22
 */
public class LinkedNodeCycle {


    public static void main(String[] args) {

        Node head1 = new Node(1);
        Node head2 = new Node(2);
        Node head3 = new Node(3);
        Node head4 = new Node(4);
        Node head5 = new Node(5);

        head1.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head5;
        head5.next = head2;

        System.out.println(isCycle(head1));
        firstCycleNode(head1);
    }

    /**
     * 入环点
     *
     * @param head
     */
    public static void firstCycleNode(Node head) {
        Node p1 = head;
        Node p2 = head;
        a:
        while (p1 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) {
                // 第一次相遇：让一个指针回到head，另外一个以1step的方式继续前进，直到下次相遇，就是入环点，可用数学证明
                // 数学比写代码有意思多了。
                p1 = head;
                for (; ; ) {
                    p1 = p1.next;
                    p2 = p2.next;
                    if (p1 == p2) {
                        System.out.println("入环node：data=" + p1.data);
                        break a;
                    }
                }

            }
        }

    }


    public static boolean isCycle(Node head) {
        Node p1 = head;
        Node p2 = head;
        boolean firstCycle = false;
        int stepCount = 0;
        while (p1 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            stepCount++;
            if (p1 == p2) {
                if (!firstCycle) {
                    firstCycle = true;
                    stepCount = 0;
                    continue;
                }
                System.out.println("环的长度=" + stepCount);
                return true;
            }
        }
        return false;
    }


    static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

}
